package skewreduce.lsst;

import java.util.HashMap;
import java.util.List;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Poligonizer {
	private static final Logger LOG = LoggerFactory.getLogger(Poligonizer.class);
	
	private static final Coord[] directions = {
		new Coord(0,-1),
		new Coord(1,-1),
		new Coord(1,0),
		new Coord(1,1),
		new Coord(0,1),
		new Coord(-1,1),
		new Coord(-1,0),
		new Coord(-1,-1),
		new Coord(0,-1),
		new Coord(1,-1),
		new Coord(1,0),
		new Coord(1,1),
		new Coord(0,1),
		new Coord(-1,1),
		new Coord(-1,0),
		new Coord(-1,-1),
		new Coord(0,0)
	};
	
	private Coord dirNext;
	private HashMap<Coord,Coord> objMap;
	
	public void findPoly(List<? extends Coord> o, List<Coord> vertices) {
	    // Idea #3:
	    // Curve-trace.  I think this is workable.
	    // Start from arbitrary known point and vector.  We'll pick the
	    // top-most and left-most pixel.  Trace the object edge clockwise
	    // until we return to the starting point.

	    // Step 1: put pixels into hash table. O(n)
		objMap = new HashMap<Coord,Coord>();
		for ( Coord c : o ) {
			objMap.put(c, c);
		}
		Coord initPos = o.get(0);
		for ( Coord c : o ) {
			if ( c.compareTo(initPos) < 0 ) {
				initPos = c;
			}
		}
		
	    // Step 2: Find left-most, top-most pixel. O(n)
	    Coord current = initPos;
	    Coord next;
	    // Initial direction: Upwards and left
	    Coord dir = directions[15];
	    Coord initDir;
	    vertices.clear();
	  
	    //  std::cout << "Finding poly from " <<  o.size() << " pixels" << "in map " << pixels.size() << std::endl;
	    // Prime next pixel
	    next = chooseNext(current, dir);
	    initDir = dirNext;
	    dir = dirNext;

	    do {
			// Add point to polygon.
			vertices.add(current);
			current = next;
			// Choose next pixel
			next = chooseNext(current, dir);
			if ( vertices.size() > (2 + 2*o.size()) ) {
				LOG.warn("Oversize for object. Bailing out");
				break;
			}
			dir = dirNext;

	    } while ( (current != initPos) || (dir != initDir) );  
	  
	}

	private Coord chooseNext(Coord loc, Coord dir) {
	    int index;
	    int leftTurn = 1;
	    Coord prosp;

	    if ( objMap.size() == 1) return loc; // There is no next.

	    // Compensate for diagonals: okay to turn 90 degrees left for them.
	    if ( 2 == (dir.getX()*dir.getX()) + (dir.getY()*dir.getY()) ) { // diagonal?
	    	leftTurn = 2;
	    }
	    // Seek to current direction.
	    for ( index = leftTurn; ! directions[index].equals(dir); ++index );
	    // Then back-off two: while tracing, we can at most turn left 90deg
	    index -= leftTurn;
	    // std::cout << "OldDir:" << dir.first << "," << dir.second << "  "
	    //      << "searchfrom: " << _directions[index].first
	    //      << "," << _directions[index].second << std::endl;

	    Coord obj = null;
	    do {
	    	prosp = loc.add(directions[index]);
	    	obj = objMap.get(prosp);
	    	++index;
	    	if ( index > 17 ) {
	    		throw new IllegalStateException();
	    	}
	    } while ( obj == null );
	    
	    // We are guaranteed to find one, unless the the object only has one
	    // pixel.
	    dirNext = directions[index-1]; // -1 to reverse the loop increment.

	    return obj; // return the coord.
	}
}
